/*
 * Copyright (c) 2022.版权所有高金磊
 */

package 领扣算法.AA中等题.查找和最小的K对数字1;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    //内存超出限制
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> data=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]+o1[1]-o2[0]-o2[1];
            }
        });
        for (int i = 0; i < Math.min(nums1.length,k); i++) {
            for (int j = 0; j < Math.min(nums2.length,k); j++) {
                data.add(new int[]{nums1[i],nums2[j]});
            }

        }
        LinkedList<List<Integer>> res=new LinkedList<>();
        while (k-->0){
            if (data.isEmpty())
                break;
            LinkedList<Integer> middle=new LinkedList<>();
            int[] ints=data.poll();
            middle.add(ints[0]);
            middle.add(ints[1]);
            res.add(middle);
        }
        return res;

    }
}
